package complexdatastructure.unionfindset;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Classname : ConnectingCitiesWithMinimumCost
 * @Description :
 * <a href="https://leetcode.cn/problems/connecting-cities-with-minimum-cost/">1135. 最低成本联通所有城市</a>
 * @Author : chentianyu
 * @Date 2023/2/11 22:07
 */


public class ConnectingCitiesWithMinimumCost {
    public int minimumCost(int n, int[][] connections) {
        int cost = 0;
        // 将边根据成本排序
        Arrays.sort(connections, Comparator.comparingInt(o -> o[2]));
        // 并查集合并
        UF uf = new UF(n);
        for (int[] connection : connections) {
            int u = connection[0], v = connection[1], w = connection[2];
            if (uf.union(u, v)) cost += w;  // 成功合并才累加成本
        }
        if (uf.getUnionNum() + 1 != n) return -1;
        return cost;
    }

    class UF {
        private int[] parent;
        private int[] rank;
        private int n;  // 节点数量
        private int unionNum;  // 合并次数

        public UF(int n) {
            this.parent = new int[n + 1];
            this.rank = new int[n + 1];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public int find(int x) {
            return x == this.parent[x] ? x : (this.parent[x] = find(this.parent[x]));
        }

        public boolean union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x == y) return false;  // 说明两个节点已经在同一集合，合并失败
            if (rank[x] >= rank[y]) {
                if (rank[x] == rank[y]) rank[x]++;
                this.parent[y] = x;
            } else {
                this.parent[x] = y;
            }
            this.unionNum++;
            return true;
        }

        public int getUnionNum() {
            return this.unionNum;
        }
    }
}
